// HashTable.h
//
// Linked list-based hash table.
//
#ifndef __HASHTABLE_H__
#define __HASHTABLE_H__

#include "util/Pool.h"
#include "util/List.h"
#include "util/Logger.h"
#include "base/simtypes.h"

template <class K, class D>
class HashTableNode {
 public:
    // overloaded to force use of CALLOC/FREE
    NEW_DELETE_OPERATORS_INLINE_H(HashTableNode,NoSuper);
    HashTableNode();
    ~HashTableNode();

    K  key;
    D  data;

    HashTableNode* next;
};

template <class K, class D>
class HashTable {
 public:
    // overloaded to force use of CALLOC/FREE
    NEW_DELETE_OPERATORS_INLINE_H(HashTable,NoSuper);
    //
    // HashTable(int size, unsigned int (*toInt)(K*))
    //
    // size is number of entries in linked-list table (not the max number of
    //   entries in the hashtable)
    // toInt takes a key and returns an integer. the returned int does not
    //   have to be in any certain range. will be %'d by size to hash.
    //
    HashTable(int htsize, unsigned int (*toInt)(K));
    virtual ~HashTable();

    // Visitor may modify the data item if desired.  If the visitor
    // returns false the entry will be removed (and removing() will be
    // called).  It is the visitors responsibility to delete the data
    // item if that is required.
    virtual void         visit(bool (*visitor)(K, D&, void*), void*);

    // Returns the previous value, or 0 if none.
    virtual D            put(K key, D data);

    // Asserts that key is not already in the table.
    virtual void         insert(K key, D data);

    // Asserts that the key is in the table.
    virtual D            remove(K key);

    virtual void         merge(HashTable<K, D>*);

    virtual D            lookup(K key) const;
    virtual bool         contains(K key) const;

    // Calls implicitRemoval() for all entries in the hash.
    virtual void         clear(void (*deleter)(K, D) = NULL);

    virtual unsigned int hash(K key) const;

    virtual uint         getLength() const;
    virtual bool         isEmpty() const;
    virtual List<D>*     getList() const;
    virtual List<K>*     getKeyList() const;

 protected:
    unsigned int (*toInt)(K key);

    /**
       htsize is the number of buckets in the hash table
    
       the name of the size variable was changed to htsize to avoid
       conflicts with child classes
    */
    uint htsize;
    
    /**
       length is the number of elements in the table
    */
    uint length;

    /** 
        The Java specification uses this as a threshold value.
    */
    static const float LoadFactor; // = 0.75;
    
    /** 
        threshold is the number of elements after which the load
        factor is exceeded. if we could rehash, we would do it
        here. For now we just warn that they should increase the
        initialize capacity.
    */
    uint threshold;

    HashTableNode<K,D>** table;

    virtual HashTableNode<K,D>* lookupInternal(K key) const;

    // Called when removing without a call to remove().  This can
    // happen during removal from a visitor and during a clear().
    virtual void                implicitRemoval (K key, D data);

    // the following methods are only to avoid a compiler problem with
    // inheritance of 2 templates. note that it should be a protected function.
    // TODO: nbronson: get rid of CacheHash dependency on HashTable internal implementation details
    virtual HashTableNode<K,D>** getTable() const;
};

/// Implementation ///
template <class K, class D>
const float HashTable<K,D>::LoadFactor = 0.75;

template <class K, class D>
HashTableNode<K,D>::HashTableNode ()  { }

template <class K, class D>
HashTableNode<K,D>::~HashTableNode () { }

template <class K, class D>
HashTable<K,D>::HashTable(int _htsize, unsigned int (*_toInt)(K)) :
    toInt(_toInt),
    htsize(_htsize),
    length(0),
    threshold((uint)(_htsize*LoadFactor)),
    table((HashTableNode<K,D>**)CALLOC(htsize, sizeof(HashTableNode<K,D>*))) {
}

template <class K, class D>
HashTable<K,D>::~HashTable() {
    ASSERT(isEmpty());
    FREE(table);
}

template <class K, class D>
void HashTable<K,D>::merge (HashTable<K,D>* other) {
    ASSERT(other->toInt == toInt);
    ASSERT(other->htsize == htsize);

    for (uint i = 0; i < htsize; i++) {
        HashTableNode<K,D>* walk = other->table[i];
        while (walk != NULL) {
            if (!contains(walk->key)) {
                insert(walk->key, walk->data);
            }
            walk = walk->next;
        }
    }
}

template <class K, class D>
D HashTable<K,D>::put (K key, D data) {
    HashTableNode<K,D>* existing = lookupInternal(key);
    if (existing != NULL) {
        D prev = existing->data;
        existing->data = data;
        return prev;
    } else {
        int place = hash(key);

        HashTableNode<K,D>* node = NEW HashTableNode<K,D>;
        node->key = key;
        node->data = data;

        node->next = table[place];
        table[place] = node;

        length++;
        if (length > threshold) {
            Log->w("HashTable %s exceeded load factor(%f) with length=%d threshold=%d htsize=%d\n",
                   typeid(this).name(),
                   LoadFactor,
                   length,
                   threshold,
                   htsize);
            Log->printStackTrace(SEV_WARNING);
            threshold *= 2;
        }
        return 0;
    }
}

template <class K, class D>
void HashTable<K,D>::insert (K key, D data) {
    // austenmc: im now allowing multiple entries w/ the same key; this is
    // to simplify nesting...
    // ASSERT(lookupInternal(key) == NULL);

    int place = hash(key);

    HashTableNode<K,D>* node = NEW HashTableNode<K,D>;
    node->key = key;
    node->data = data;

    node->next = table[place];
    table[place] = node;

    length++;
    if (length > threshold) {
        Log->w("HashTable %s exceeded load factor(%f) with length=%d threshold=%d htsize=%d\n",
               typeid(this).name(),
               LoadFactor,
               length,
               threshold,
               htsize);
        Log->printStackTrace(SEV_WARNING);
        threshold = (uint)-1;
    }
}

template <class K, class D>
void HashTable<K,D>::visit (bool (*visitor)(K, D&, void* data), void* data) {
    for (uint place = 0; place < htsize; place++) {
        HashTableNode<K,D>* walk = table[place];
        HashTableNode<K,D>* prev = NULL;

        while (walk) {
            if (!visitor(walk->key, walk->data, data)) {
                implicitRemoval(walk->key, walk->data);

                if (prev == NULL) {
                    table[place] = walk->next;
                    delete walk;
                    walk = table[place];
                } else {
                    prev->next = walk->next;
                    delete walk;
                    walk = prev->next;
                }

                length--;
            } else {
                prev = walk;               
                walk = walk->next;
            }
        }
    }
}

template <class K, class D>
D HashTable<K,D>::remove (K key) {
    int place = hash(key);
    D data;

    HashTableNode<K,D>* walk = table[place];
    HashTableNode<K,D>* prev = NULL;

    while (walk) {
        if (walk->key == key) {
            data = walk->data;
            if (prev == NULL) {
                table[place] = walk->next;
            } else {
                prev->next = walk->next;
            }
            delete walk;
            length--;
 
            return data;
        }
        prev = walk;
        walk = walk->next;
    }

    // don't call this unless you know its in the table
    ASSERT(false);
    // this line is just to remove compiler warning
    data = walk->data;
    return data;
}

template <class K, class D>
void HashTable<K,D>::implicitRemoval (K key, D data) {
}

template <class K, class D>
HashTableNode<K,D>* HashTable<K,D>::lookupInternal (K key) const {
    int place = hash(key);

    HashTableNode<K,D>* walk = table[place];
    HashTableNode<K,D>* prev = NULL;

    while (walk) {
        if (walk->key == key) {
            // you found it: let's move it to the front w/ the assumption
            // that we'll look it up again...
            if (prev != NULL) {
                prev->next = walk->next; 
                walk->next = table[place];
                const_cast<HashTableNode<K,D>**>(table)[place] = walk;
            }
            return walk;
        }
        prev = walk;
        walk = walk->next;
    }

    // NULL means no entry found, not NULL data value
    return NULL;
}

template <class K, class D>
D HashTable<K,D>::lookup (K key) const {
    HashTableNode<K,D>* node = lookupInternal(key);
    if (node == NULL) {
        return (D)NULL;
    }
    return node->data;
}

template <class K, class D>
bool HashTable<K,D>::contains(K key) const {
    HashTableNode<K,D>* node = lookupInternal(key);
    return (node != NULL);
}

template <class K, class D>
void HashTable<K,D>::clear (void (*deleter)(K, D)) {
    if (length == 0) {
        return;
    }
    for (uint i = 0; i < htsize; i++) {
        HashTableNode<K,D>* walk = table[i];
        while (walk != NULL) {
            implicitRemoval(walk->key, walk->data);

            if (deleter != NULL) {
                deleter(walk->key, walk->data);
            }

            HashTableNode<K,D>* const victim = walk;
            walk = walk->next;

            delete victim;
        }
        table[i] = NULL;
    }

    length = 0;
}

template <class K, class D>
unsigned int HashTable<K,D>::hash (K key) const {
    return toInt(key) % htsize;
}

template <class K, class D>
uint HashTable<K,D>::getLength () const {
    return length;
}

template <class K, class D>
bool HashTable<K,D>::isEmpty () const {
    return (getLength() == 0);
}

template <class K, class D>
List<D>* HashTable<K,D>::getList () const {
    List<D>* l = NEW List<D>;
    for (uint i = 0; i < htsize; i++) {
        HashTableNode<K,D>* walk = table[i];
        while (walk) {
            l->add(walk->data);
            walk = walk->next;
        }
    }

    ASSERT(l->size() == length);

    return l;
};

template <class K, class D>
List<K>* HashTable<K,D>::getKeyList () const {
    List<K>* l = NEW List<K>;
    for (uint i = 0; i < htsize; i++) {
        HashTableNode<K,D>* walk = table[i];
        while (walk) {
            l->add(walk->key);
            walk = walk->next;
        }
    }

    ASSERT(l->size() == length);

    return l;
};


template <class K, class D>
HashTableNode<K,D>** HashTable<K,D>::getTable() const
{
    return table;
}

inline unsigned int uintToInt (uint key) { return (unsigned int) (key >> 6); };
inline unsigned int voidStarToInt (void* key) { return uintToInt((uint)key); };
inline unsigned int VAtoUint (VA key) { return (uint)key; };

#endif // __HASHTABLE_H__
